package com.leetcode.algorithm.topic;

import com.leetcode.algorithm.common.ListNode;

/**
 * 链表相关算法题解
 *  单链表
 *  带头结点的单链表
 *  双链表
 *  循环双链表
 *  
 * (done)141. 环形链表
 * @author: jie.deng
 * @time: 2019年4月16日 上午11:47:39
 */
public class LinkedListSolution {
    /**
     * 141. 环形链表 
     * 给定一个链表，判断链表中是否有环。
     * 
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
     * 
     * 示例 1：
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * 
     * 示例 2：
     * 输入：head = [1,2], pos = 0
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * 
     * 示例 3：
     * 输入：head = [1], pos = -1
     * 输出：false
     * 解释：链表中没有环。
     * 
     * 进阶：
     * 
     * 你能用 O(1)（即，常量）内存解决此问题吗？
     * 
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // Initialize slow & fast pointers
        ListNode slow = head;
        ListNode fast = head;
        /**
         * Change this condition to fit specific problem.
         * Attention: remember to avoid null-pointer error
         **/
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;           // move slow pointer one step each time
            fast = fast.next.next;      // move fast pointer two steps each time
            if (slow == fast) {         // change this condition to fit specific problem
                return true;
            }
        }
        return false;   // change return value to fit specific problem
    } 
    
}

// Definition for singly-linked list.
class SinglyListNode {
    int val;
    SinglyListNode next;

    SinglyListNode(int x) {
        val = x;
    }
}

// Definition for doubly-linked list.
class DoublyListNode {
    int val;
    DoublyListNode next, prev;

    DoublyListNode(int x) {
        val = x;
    }
}
